class Solution {
public:
    public:
    unordered_map<long long,int> hashtable;
    //前缀和
    int recursion(TreeNode* root,const int& targetSum,long long cur)
    {
        if(!root){
            return 0;
        }
        int ret = 0;
        cur += root->val;
        if(cur == targetSum){
            ++ret;
        }
        if(hashtable.count(cur - targetSum)){
            ret += hashtable[cur-targetSum];
        }
        hashtable[cur]++;
        ret += recursion(root->left,targetSum,cur);
        ret += recursion(root->right,targetSum,cur);
        if(--hashtable[cur] == 0){
            hashtable.erase(cur);
        }
        return ret;
    }
    int pathSum(TreeNode* root,int targetSum)
    {
        if(!root){
            return 0;
        }
        return recursion(root,targetSum,0);
    }
};